package com.zq.solution.string;

import java.util.Arrays;

/**
 * @ClassName LongestCommonPrefix
 * @Description 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""
 * @Author ZQ
 * @Date 2020/10/12 14:24
 * @Version 1.0
 */
public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] strs) {
        int strsLength = strs.length;
        if (strsLength < 1){
            return "";
        }else if (strsLength == 1) {
            return strs[strsLength -1];
        }else if (strs[strsLength - 1].equals("")){
            return "";
        }else{
            StringBuilder commonPre = new StringBuilder();
            String s1 = strs[strsLength - 1];
            String s2 = strs[strsLength - 2];
            int length = Math.min(s1.length(), s2.length());
            for (int i = 0; i < length; i++){
                if (s1.charAt(i) == s2.charAt(i)){
                    commonPre.append(s2.charAt(i));
                }else{
                    break;
                }
            }
            strs[strsLength-2] = commonPre.toString();
            return longestCommonPrefix(Arrays.copyOf(strs, strsLength-1) );
        }
    }

    public static void main(String[] args) {
        String[] s = new String[]{"flower","flow","flight"};
        System.out.println(longestCommonPrefix(s));
    }
}
